The invention pertains to digital data processing and, more particularly, to improved methods and apparatus for performing median filter operations.
A wide variety of computing and image processing applications call for the processing of two dimensional images, typically for printing the image or for electronic display such as by display on a computer screen. Very often, the images needing display will have any number of random, impulse or single pixel noise problems that can be corrected using an appropriate filtering technique. One popular filtering technique for addressing these noise issues is median filtering. A median filter computes the output value of each pixel in an image as the median value of pixels in a small neighborhood around the pixel of interestxe2x80x94essentially replacing each pixel output with the median output value of its neighborhood. A common neighborhood used in median filtering is a 9-pixel, 3xc3x973 square centered on the pixel of interest.
Because images can contain large numbers of pixels, and also because some applications call for the filtering of large numbers of images, execution time for calculating medians has a large impact on the performance of the software applications that employ median filtering. One approach to improving the performance of median filters has been to perform the filtering using SIMD processors. In a SIMD (single instruction, multiple data) processor, a single instruction operates on a vector register that holds multiple values. This is in contrast to a conventional processor in which each instruction operates on only a single data value. One class of recent SIMD processors employ the AltiVec(trademark) technology, of Motorola, that is capable of concurrently operating on vectors with 4, 8 or 16 values.
Notwithstanding the benefits of array processors such as the AltiVec(trademark), image processing times can be significantly reduced by even slight improvements in methods for calculating medians or in programming techniques that increase the throughput of median calculations through the array processor, the throughput typically being measured in clock cycles per pixel, or alternatively in clock cycles per (16 byte) vector.
In view of the foregoing, an object of the invention is to provide improved methods and apparatus for digital image processing.
A more particular object is to provide such methods and apparatus as permit the rapid execution of median filtering on a two dimensional data set.
These and other objects are attained by the present invention which provides, in some aspects, novel methods for calculating median filter values that increase the speed with which the calculation can be performed.
A method according to one aspect of the invention provides for rapidly performing a median filter calculation for a value at a predetermined position in a matrix of values representing a neighborhood about the predetermined position. The method includes ordering the values in each column of the matrix to create an ordered matrix; determining a maximum value for a row of the ordered matrix having the lowest values; determining a median value for a row of the ordered matrix having middle values; and determining a minimum value for a row of the ordered matrix having the highest values. Based on these determinations, the median filter value for the neighborhood can be calculated as a median value of the maximum value for a row of the ordered matrix having the lowest values, median value for a row of the ordered matrix having middle values, and minimum value for a row of the ordered matrix having the highest values. The calculated median filter value can then be output as necessary. The rows of the matrices can conveniently be represented as vectors and the ordering and determining steps can be performed as vector operations.
In a further aspect, the invention provides a method for rapidly performing a plurality of median filter calculations for a value at a predetermined position in a matrix of values representing a 3xc3x973 neighborhood about the predetermined position. The method includes inputting rows for median filtering, the number of rows being one more than the number of rows in the neighborhood; presorting rows that will participate in more than one median filter calculation; separating the input rows into separate matrices, each having the pre-sorted rows and one unsorted row; ordering the values in each column of each matrix to result in ordered matrices; determining a maximum value for a row of each ordered matrix having the lowest values; determining a median value for a row of each ordered matrix having middle values determining a minimum value for a row of each ordered matrix having the highest values; and determining the median filter values as a median value of the previously determined maximum value for a row of each ordered matrix having the lowest values, median value for a row of each ordered matrix having middle values, and minimum value for a row of each ordered matrix having the highest values.
In either aspect, the matrix rows can be represented as vectors that include more than three values, and thus more values than are found in a 3xc3x973 neighborhood for a single median filter calculation. The calculations on the ordered matrices can be performed using vector operations to simultaneously result in a plurality of triplet maximum, median and minimum values stored in a single output vector. The calculation of the median filter value corresponding to the plurality of triplet maximum, median and minimum values can then also be carried out with four vector operations to simultaneously produce a plurality of median filter results. In addition, vector loading and processing instructions can be interleaved to reduce the overall number of clock cycles. An apparatus and computer code product for carrying out the invention are also described.
These and other aspects of the invention have the advantage of permitting rapid median filter calculations without excessive use of system resources.